package com.demo.java.OD351_400.OD367;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【区间交集(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146226142
 */
public class OdMain {

    // 定义一个区间类
    static class Interval {
        int start;
        int end;

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    // 创建一个区间
    public static Interval createInterval(int s, int e) {
        return new Interval(s, e);
    }

    // 合并重叠的区间
    public static Interval[] mergeIntervals(Interval[] intervals) {
        List<Interval> merged = new ArrayList<>();
        int mergedIndex = 0;

        for (int i = 0; i < intervals.length; i++) {
            Interval interval = intervals[i];
            // 如果 merged 为空，或者当前区间的起始位置大于 merged 中最后一个区间的结束位置
            if (mergedIndex == 0 || interval.start > merged.get(mergedIndex - 1).end) {
                // 直接将当前区间添加到 merged 中
                merged.add(interval);
                mergedIndex++;
            } else {
                // 否则更新 merged 中最后一个区间的结束位置为当前区间结束位置和原结束位置中的最大值
                merged.get(mergedIndex - 1).end = Math.max(merged.get(mergedIndex - 1).end, interval.end);
            }
        }

        return merged.toArray(new Interval[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Interval> inputIntervals = new ArrayList<>();

        // 逐行读取输入的区间，创建 Interval 对象并存储在 inputIntervals 列表中
        while (scanner.hasNextInt()) {
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            inputIntervals.add(createInterval(left, right));
        }

        // 按照区间的起始位置进行排序
        Collections.sort(inputIntervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });

        Interval[] combinedIntervals = new Interval[100];
        int combinedIndex = 0;
        int r = -1_000_000_000;

        // 寻找交集并将它们合并
        for (int i = 0; i < inputIntervals.size(); i++) {
            Interval interval = inputIntervals.get(i);
            if (interval.end < r) {
                continue;
            }
            r = interval.end;
            for (int j = i + 1; j < inputIntervals.size(); j++) {
                Interval nextInterval = inputIntervals.get(j);
                if (interval.end < nextInterval.start) {
                    break;
                } else if (interval.end == nextInterval.start) {
                    combinedIntervals[combinedIndex++] = createInterval(interval.end, interval.end);
                    break;
                } else {
                    int minEnd = Math.min(interval.end, nextInterval.end);
                    combinedIntervals[combinedIndex++] = createInterval(nextInterval.start, minEnd);
                }
            }
        }

        // 输出合并后的区间
        if (combinedIndex == 0) {
            System.out.println("None");
            return;
        }

        // 调用合并函数合并重叠区间
        Interval[] mergedIntervals = mergeIntervals(Arrays.copyOf(combinedIntervals, combinedIndex));
        for (Interval interval : mergedIntervals) {
            System.out.println(interval.start + " " + interval.end);
        }
    }
}